﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;

namespace PetGo
{
    partial class Tree
    {
        
        public static double b = 0.005;
        public static double c = 0.00001;
        public Tree myparent;
        public Dictionary<int, Tree> mychilds;
        public Dictionary<int, int> mychildRaveVorkommen = new Dictionary<int, int>();
        public Dictionary<int, int> mychildRaveGewonnen = new Dictionary<int, int>();
        public Dictionary<int, double> mychildBias = new Dictionary<int, double>();
        public Dictionary<int, int> patternmoves1 = null;
        //public Dictionary<int, int> mychildIgnore = new Dictionary<int, int>();

        //public Dictionary<int, int> mychildOppRaveVorkommen = new Dictionary<int, int>();
        //public Dictionary<int, int> mychildOppRaveGewonnen = new Dictionary<int, int>();

        public int myStartpos;
        public color myColor;
        public static Random Random = new Random();
        //public static int permutatedTeeNodeCount = 0;
        public static int writetop = 5;
        public static int mypathlength;

        public int anz;

        public static Dictionary<int, int> myweakGroups = new Dictionary<int, int>();
        public static Dictionary<int, int> myaliveGroups = new Dictionary<int, int>();
        public static Board myRootBoard;
        public static List<int> myMoveHistory;
        public static Board playOutBoard;
        public static Dictionary<int, int> mylastMoveCache3 = new Dictionary<int, int>();
        public static Dictionary<int, int> mylastMoveCache2 = new Dictionary<int, int>();
        public static Dictionary<int, int> mylastMoveCache1 = new Dictionary<int, int>();
        public static List<int> myTopMoves = new List<int>();
        //public static List<int> myOppTopMoves = new List<int>();

        public static Dictionary<int, int> backpos = new Dictionary<int, int>();


        public int pos;
        public double wert;
        public int gewonnen;
        public volatile int vorkommen;
        public int gewonnen_RAVE;
        public int vorkommen_RAVE;
        //public int verloren_RAVE;
        public double q;
        public double qr;
        public double myresultpoints;
        public double mybias;
        //public double zufall;
        //public double ergebnis_punkte;

        public Tree(Tree theParent, Board theBoard)
        {
            if (theBoard != null)
            {
                myRootBoard = theBoard.Copy();
                myRootBoard.fillEmptyFieldsList();
                myMoveHistory = theBoard.mymovehistory;
            }
            myparent = theParent;
            if (myparent == null)
            {
                mylastMoveCache1 = null;
                mylastMoveCache2 = null;
                mylastMoveCache3 = null;
                //Tree.biasCache.Clear();
                myColor = myRootBoard.getopponent(theBoard.mytoMove);
                Group.myRadCache.Clear();
            }
            else
            {
                myColor = myRootBoard.getopponent(myparent.myColor);
            }

            //mychilds = new Dictionary<int, Treenode>();
            //zufall = (double)((double)Random.Next(0, 100)) / 20000000;

        }
        public void initAsRootTree(Board theBoard)
        {
            mylastMoveCache1 = null;
            mylastMoveCache2 = null;
            mylastMoveCache3 = null;
            //Tree.biasCache.Clear();
            Group.myRadCache.Clear();
            myparent = null;
            myRootBoard = theBoard.Copy();
            myMoveHistory = theBoard.mymovehistory;
            reduceStartpos();
        }

        public void reduceStartpos()
        {
            if (myStartpos > 0) --myStartpos;
            if (mychilds != null)
            {
                foreach (Tree theChild in mychilds.Values)
                {
                    theChild.reduceStartpos();
                }
            }
        }

        public void doTreenode()
        {
            if (myparent != null)
            {
                playOutBoard.place(pos, myColor);
                playOutBoard.changemycolortoMove();
                myStartpos = playOutBoard.mymovehistory.Count;
                //watch the search tree
                //playOutBoard.writeboardandwait();
            }
            if (patternmoves1 == null)
            {
                patternmoves1 = new Dictionary<int, int>();
                getPatternMoves();
            }
            if (vorkommen > 0 || myparent == null)
            {
                doTreePolicy();
            }
            else
            {
                doDefaultPolicy();
            }
        }

        public void doTreeRoot()
        {
            int dominimum = 0;
            anz = 0;
            if (myRootBoard.mytoMove == color.white)
            {
                b = 0.006;
                c = 0.001;
                //b = 0;
                //c = 0;
                //b = 0.003;
                //c = 0.01;
                b = 0.008;
                c = 0.0001;
                //b = 0.0000001;
                //c = 0.0000000000001;
            }
            else
            {
                b = 0.006;
                c = 0.000002;
                //b = 0;
                //c = 0;
            }
            //b = 0.004;
            //c = 0.0001;
            //b = 0.0000001;
            //c = 0.0000000000001;
            //b = 0.001;
            //c = .01;
            //b = 0.001;
            //if (myMoveHistory.Count > 0)
            //{
            //    b = 0.001 + myMoveHistory.Count*0.0001;
            //}
            //c = 0.0000000000001;
            b = 0.006;
            c = 0.000002;
            logMoveHist = Math.Log(myMoveHistory.Count + 1);
            //sqrtMoveHist = Math.Sqrt((myMoveHistory.Count + 1)/2);

#if DEBUG
            dominimum = 1000;

#endif

            Stopwatch theStart = new Stopwatch();
            theStart.Start();
            //myStartposBiasCache.Clear();
            myRootBoard.myGame.myDynamicKomi = Double.MinValue;
            getweakGroups();
            //getaliveGroups();
            bool stopit = false;
            while (((theStart.ElapsedMilliseconds < 1000 * myRootBoard.myGame.mysecondstothink || anz < dominimum) && vorkommen < Game.mymaxPlayouts && !stopit))
            {
                anz = enlargeTree(anz);
                Tree thetop = getTopChild();
                Tree thesec = getTopChild(2);
                int vsec = 0;
                if (thesec != null) vsec = thesec.vorkommen;
                if (thetop != null)
                {
                    int diff = thetop.vorkommen - vsec;
                    double canbe = ((double)1000 * myRootBoard.myGame.mysecondstothink - theStart.ElapsedMilliseconds) * anz / theStart.ElapsedMilliseconds;
                    if (diff > canbe)
                    {
                        stopit = true;
                        //#if DEBUG           
                        //                    Console.WriteLine("# elapsed:" + theStart.ElapsedMilliseconds.ToString());
                        //#endif
                    }
                }
#if DEBUG
                    stopit = false;
#endif
            }
            foreach(Group cGroup in myRootBoard.myGame.myBoard.myGroup.Values)
            {
                if (myRootBoard.myGroupPosition.ContainsKey(cGroup.myposition))
                {
                    cGroup.alivestat = (double)myRootBoard.myGroup[cGroup.myposition].alive / (myRootBoard.myGroup[cGroup.myposition].alive + myRootBoard.myGroup[cGroup.myposition].dead);
                }
            }
#if DEBUG
            writealive();
#endif
            writeTreeRoot();
            Sgf.writeLog(this, myRootBoard.myGame);
        }

        //private void getaliveGroups()
        //{
        //    if (myparent != null) return;
        //    myaliveGroups.Clear();
        //    foreach (Group cGroup in myRootBoard.myGame.myBoard.myGroup.Values)
        //    {
        //        if (cGroup.alivestat > 0.98 || cGroup.myEyes.Count>1)
        //        {
        //            myaliveGroups[cGroup.myposition] = cGroup.myposition;
        //        }
        //    }
        //}

        private void getweakGroups()
        {
            if (myparent != null) return;
            myweakGroups.Clear();
            foreach(Group cGroup in myRootBoard.myGame.myBoard.myGroup.Values)
            {
                if (cGroup.myFields.Count > 3 && cGroup.alivestat > 0.4 && cGroup.alivestat < 0.75)
                {
                    myweakGroups[cGroup.myposition] = cGroup.myposition;
                }
            }
        }

        public int enlargeTree(int anz)
        {
            playOutBoard = myRootBoard.Copy();

            Board.myPlayOutTopMoves = new List<int>(myTopMoves);
            doTreenode();
            // Nur für die Root wird hier gezählt
            ++vorkommen;
            ++anz;
            Group.aliveCount(myRootBoard, playOutBoard);
            backpropagation_perm();
            if (anz % 50 == 0)
            {
                getTop20PercentSorted(this);
            }
#if DEBUG
            if (anz % 1000 == 0 && !myRootBoard.myGame.myisGTP)
            {
                for (int i = 0; i < writetop; ++i) Console.WriteLine();
                mypathlength = 0;
                Console.SetCursorPosition(0, Console.CursorTop - writetop);
                writemovePath(this);
            }
#endif
            return anz;
        }

        private void backpropagation_perm()
        {
            //if (playOutBoard.myWinner == color.empty)
            //{
            //    ;
            //}
            //if (playOutBoard.myWinner == color.black)
            //{
            //    ;
            //}
            if (mychilds != null && mychilds.Count > 0 && playOutBoard.myWinner != color.empty)
            {
                if (myStartpos < playOutBoard.mymovehistory.Count && mychilds.ContainsKey(playOutBoard.mymovehistory[myStartpos]))
                {
                    mychilds[playOutBoard.mymovehistory[myStartpos]].backpropagation_perm();
                }
            }
            backPropagation();
        }

        public void doTreePolicy()
        {
            if (mychilds == null || mychilds.Count == 0) createChilds(playOutBoard.mytoMove);
            int theZugposition = treeSelection();
            if (theZugposition == -1)
            {
                playOutBoard.playout(this);
                return;
            }
            createChild(theZugposition);
            mychilds[theZugposition].doTreenode();
        }

        public void doDefaultPolicy()
        {
            //playOutBoard.writeboardandwait();
            createChilds(playOutBoard.mytoMove);
            //if (myRootBoard.mytoMove == color.white)
            //{
            //int times = 2;
            ////if (times < 1) times = 1;
            //Board thesave = playOutBoard.Copy();
            //foreach (int i in playOutBoard.mymovehistory) thesave.mymovehistory.Add(i);

            //for (int x = 0; x < times + 1; ++x)
            //{
            //    if (x > 0)
            //    {
            //        playOutBoard = thesave.Copy();
            //        foreach (int i in thesave.mymovehistory) playOutBoard.mymovehistory.Add(i);
            //    }
            //    playOutBoard.playout(this);
            //    Tree theRoot = this;
            //    while (theRoot.myparent != null) theRoot = theRoot.myparent;
            //    theRoot.backpropagation_perm();
            //}
            //}
            //else
            {
                playOutBoard.playout(this);
                //Tree theRoot = this;
                //while (theRoot.myparent != null) theRoot = theRoot.myparent;
            }
        }


        public int treeSelection()
        {
            int theZugPosition = -1;
            int badmove = -1;
            //logMoveHist = Math.Log(myMoveHistory.Count + 1);
            double maxWert = Double.MinValue;
            double minWert = Double.MaxValue;
            //if (myMoveHistory.Count < 10 && mychildRaveVorkommen.Count > 0)
            //{
            //    theZugPosition = mychildRaveVorkommen.ElementAt(Tree.Random.Next(mychildRaveVorkommen.Count)).Key;
            //    maxWert = calculateMCTSResult(theZugPosition);
            //}
            
            double maxQr = maxWert;
            double minQr = minWert;


            foreach (int pos in mychildRaveVorkommen.Keys)
            {
                //if (mychildIgnore.ContainsKey(pos))
                //{
                //    continue;
                //}
                maxQr = calculateMCTSResult(pos);
                if (theZugPosition>-1)
                {
                    //if (mychildRaveVorkommen[pos] > 150)
                    //{
                    //    if ((mychildRaveGewonnen[pos] + .5) / (mychildRaveVorkommen[pos] + 1) < ((mychildRaveGewonnen[theZugPosition] + .5) / (mychildRaveVorkommen[theZugPosition] + 1)) * 0.8)
                    //    {
                    //        mychildIgnore[pos] = pos;
                    //    }
                    //}
                }

                //if (Tree.myMoveHistory.Count < 150)
                //{
                    if (myparent != null || this.pos != 0)
                    {
                        if (Tree.myRootBoard.getdistance_int(pos, this.pos) < 10)
                        {
                            maxQr += maxQr / 1000;
                        }
                    }
                    //else
                    //{
                    //    if (Tree.myMoveHistory.Count > 0)
                    //    {
                    //        if (Tree.myRootBoard.getdistance(Tree.myMoveHistory[Tree.myMoveHistory.Count - 1], pos) < 3.1)
                    //        {
                    //            maxQr += maxQr / 1000;
                    //        }
                    //    }
                    //}
                //}
                //theChildnode.calculateMCTSResult();
                    if (maxQr > maxWert
                        //|| (calculateMCTSResult(pos) == maxWert && theChildnode.qr > maxQr)
                    )
                {
                    maxWert = maxQr;
                    //maxQr = theChildnode.qr;
                    theZugPosition = pos;
                }
                if (maxQr < minWert)
                {
                    minWert = maxQr;
                    badmove = pos;
                }
            }
            //if (myStartpos < 3 && mychildIgnore.Count>0)
            //{
            //    Console.WriteLine(myStartpos.ToString() + " " + mychildIgnore.Count.ToString());
            //}

            Board.capturemoves1.Clear();

            //if (vorkommen > 200 && mychildRaveVorkommen.Count > 20 && badmove > -1)
            //{
            //    mychildRaveVorkommen.Remove(badmove);
            //    mychildRaveGewonnen.Remove(badmove);
            //    Board.randmovescount++;
            //}
#if DEBUG
            if (//!myRootBoard.myGame.myisGTP && 
                this.myStartpos == 0 && anz == 1)
            {
                writebias();
            }
#endif

            return theZugPosition;
        }

        private void getPatternMoves()
        {
            int lastpos = -1;
            if (playOutBoard.myboardsize < 19) return;

            if (playOutBoard.mymovehistory.Count > 0)
            {
                lastpos = playOutBoard.mymovehistory[playOutBoard.mymovehistory.Count - 1];
            }
            else
            {
                if (Tree.myRootBoard.myGame.myBoard.mymovehistory.Count > 0)
                {
                    lastpos = Tree.myRootBoard.myGame.myBoard.mymovehistory[Tree.myRootBoard.myGame.myBoard.mymovehistory.Count - 1];
                }

            }

            //if (lastpos > -1)
            //{
            this.patternmoves1 = playOutBoard.getPlayOutPattern(lastpos);
            if (patternmoves1.Count == 0 && myStartpos < 2 && myMoveHistory.Count < 50)
            {
                foreach (int pos in playOutBoard.myGroupPosition.Keys)
                {
                    if (playOutBoard.myGroup[playOutBoard.myGroupPosition[pos]].myColor == this.myColor)
                    {
                        Dictionary<int, int> temp = playOutBoard.getPlayOutPattern(pos);
                        foreach (int key in temp.Keys)
                        {
                            this.patternmoves1[key] = temp[key];
                        }
                    }
                }
                //if (patternmoves1.Count > 0)
                //{
                //    ;
                //}
            }
            //}
                //if (patternmoves1.Count == 0 && Tree.myRootBoard.myGame.myBoard.mymovehistory.Count + playOutBoard.mymovehistory.Count > 2)
                //{
                //    if (playOutBoard.mymovehistory.Count > 2)
                //    {
                //        lastpos = playOutBoard.mymovehistory[playOutBoard.mymovehistory.Count - 3];
                //    }
                //    else
                //    {
                //        lastpos = Tree.myRootBoard.myGame.myBoard.mymovehistory[Tree.myRootBoard.myGame.myBoard.mymovehistory.Count - 3 + playOutBoard.mymovehistory.Count];

                //    }
                //    this.patternmoves1 = playOutBoard.getPlayOutPattern(lastpos);
                //    //Board.randmovescount += this.patternmoves1.Count;
                //}
                //if (patternmoves1.Count == 0 && Tree.myRootBoard.myGame.myBoard.mymovehistory.Count + playOutBoard.mymovehistory.Count > 4)
                //{
                //    if (playOutBoard.mymovehistory.Count > 4)
                //    {
                //        lastpos = playOutBoard.mymovehistory[playOutBoard.mymovehistory.Count - 5];
                //    }
                //    else
                //    {
                //        lastpos = Tree.myRootBoard.myGame.myBoard.mymovehistory[Tree.myRootBoard.myGame.myBoard.mymovehistory.Count - 5 + playOutBoard.mymovehistory.Count];

                //    }
                //    this.patternmoves1 = playOutBoard.getPlayOutPattern(lastpos);
                   
                //    //Board.randmovescount += this.patternmoves1.Count;
                //}
                
            //if (patternmoves1.Count>0)
            //{
            //    ++Board.randmovescount;
            //}
        }

        public void backPropagation()
        {
            //if (mychilds == null || mychilds.Count == 0) return;

            // list of used positions
            backpos.Clear();
            for (int tiefe = myStartpos; tiefe < playOutBoard.mymovehistory.Count; ++tiefe)
            {
                int pos = playOutBoard.mymovehistory[tiefe];

                if ((tiefe - myStartpos) % 2 == 0)
                {
                    //if (thepos.ContainsKey(pos) && myRootBoard.mytoMove==color.white) break;
                    if (mychildRaveVorkommen.ContainsKey(pos) && !backpos.ContainsKey(pos))
                    {
                        if (mychilds.ContainsKey(pos))
                        {
                            ++mychilds[pos].vorkommen_RAVE;
                            ++mychildRaveVorkommen[pos];
                            if (playOutBoard.myWinner == mychilds[pos].myColor)
                            {
                                ++mychilds[pos].gewonnen_RAVE;
                                ++mychildRaveGewonnen[pos];
                            }
                        }
                        else
                        {
                            //Tree theChildnode = mychilds[pos];
                            //++theChildnode.vorkommen_RAVE;
                            ++mychildRaveVorkommen[pos];
                            if (playOutBoard.myWinner != myColor)
                            {
                                ++mychildRaveGewonnen[pos];
                                //++theChildnode.gewonnen_RAVE;
                            }
                        }
                        if (tiefe == myStartpos)
                        {
                            createChild(pos);
                            Tree theChildnode = mychilds[pos];
                            ++theChildnode.vorkommen;
                            if (playOutBoard.myWinner == theChildnode.myColor)
                            {
                                ++theChildnode.gewonnen;
                                theChildnode.myresultpoints += playOutBoard.myResult;
                            }
                            else
                            {
                                theChildnode.myresultpoints -= playOutBoard.myResult;
                            }
                            
                            if (myStartpos == 0)
                            {
                                if (playOutBoard.myWinner == myColor)
                                {
                                    ++gewonnen; 
                                }
                            }

                            //if (playOutBoard.mymovehistory.Count > tiefe + 1)
                            //{
                            //    int pos1 = playOutBoard.mymovehistory[tiefe + 1];
                            //    if (theChildnode.mychildRaveVorkommen.ContainsKey(pos1))
                            //    {
                            //        theChildnode.createChild(pos1);
                            //        Tree theChildChildnode = theChildnode.mychilds[pos1];
                            //        ++theChildChildnode.vorkommen;
                            //        if (playOutBoard.myWinner == theChildChildnode.myColor)
                            //        {
                            //            ++theChildChildnode.gewonnen;
                            //            theChildChildnode.myresultpoints += playOutBoard.myResult;
                            //        }
                            //        else
                            //        {
                            //            theChildChildnode.myresultpoints -= playOutBoard.myResult;
                            //        }
                            //    }
                            //}

                        }
                    }
                }
                //else
                //{
                //    if (mychilds != null && Tree.myRootBoard.mytoMove == color.black)
                //        foreach (Tree cChild in mychilds.Values)
                //        {
                //            if (cChild.mychildRaveVorkommen.ContainsKey(pos) && !backpos.ContainsKey(pos))
                //            {
                //                if (cChild.mychilds.ContainsKey(pos))
                //                {
                //                    ++cChild.mychilds[pos].vorkommen_RAVE;
                //                    ++cChild.mychildRaveVorkommen[pos];
                //                    if (playOutBoard.myWinner != cChild.mychilds[pos].myColor)
                //                    {
                //                        ++cChild.mychilds[pos].gewonnen_RAVE;
                //                        ++cChild.mychildRaveGewonnen[pos];
                //                    }
                //                }
                //                else
                //                {
                //                    //Tree theChildnode = mychilds[pos];
                //                    //++theChildnode.vorkommen_RAVE;
                //                    ++cChild.mychildRaveVorkommen[pos];
                //                    if (playOutBoard.myWinner == myColor)
                //                    {
                //                        ++cChild.mychildRaveGewonnen[pos];
                //                        //++theChildnode.gewonnen_RAVE;
                //                    }
                //                }
                //            }
                //        }

                //}
                //else
                //{
                //    if (!mychildOppRaveVorkommen.ContainsKey(pos))
                //    {
                //        mychildOppRaveVorkommen[pos] = 0;
                //        mychildOppRaveGewonnen[pos] = 0;
                //    }
                //    if (!backpos.ContainsKey(pos))
                //    {
                //        ++mychildOppRaveVorkommen[pos];
                //        if (playOutBoard.myWinner != myColor)
                //        {
                //            ++mychildOppRaveGewonnen[pos];
                //        }
                //    }
                //}
                backpos[pos] = pos;
            }
            //if (isorignal && mychilds != null && vorkommen > 10 && Tree.myRootBoard.mytoMove == color.black)
            //{
            //    foreach (Tree cChild in mychilds.Values)
            //    {
            //        cChild.backPropagation(false);
            //    }
            //}
        }


        private void createChilds(color tomove)
        {
            if (mychilds == null) mychilds = new Dictionary<int, Tree>();
            foreach (int pos in playOutBoard.getmoves(tomove, myStartpos == 0).Keys)
            {
                mychildRaveVorkommen[pos] = 0;
                mychildRaveGewonnen[pos] = 0;
                mychildBias[pos] = GetBiasForTreeSelect19(pos) * Tree.myRootBoard.myGame.mysecondstothink / 19;
            }
        }
        private void createChild(int pos)
        {
            if (mychilds.ContainsKey(pos)) return;
            Tree theChildnode = new Tree(this, null);
            theChildnode.pos = pos;
            theChildnode.vorkommen_RAVE = mychildRaveVorkommen[pos];
            theChildnode.gewonnen_RAVE = mychildRaveGewonnen[pos];
            theChildnode.mybias = mychildBias[pos];
            mychilds.Add(pos, theChildnode);
        }
        public Tree getTopChild()
        {
            return getTopChild(1);
        }

        public Tree getTopChild(int number)
        {
            if (mychilds == null) return null;
            if (mychilds.Count < number) return null;
            var sortedDict = from entry in mychilds.Values where entry != null orderby entry.vorkommen descending, entry.wert descending, entry.qr descending select entry;
            foreach (Tree cTree in sortedDict)
            {
                --number;
                if (number == 0)
                    return cTree;
            }
            return null;
        }

        private double calculateMCTSResult(int pos)
        {
            //double bias = 0;
            //if (myRootBoard.myboardsize > 9)
            //{

            //    //bias = GetBiasForTreeSelect19(pos);
            //    //if (bias != mychildBias[pos]  / (vorkommen / (15 - 2 * logMoveHist) + 1))
            //    //{
            //    //    ;
            //    //}
            //}
            //if (myStartpos > 0 && mychildBias[pos] / (vorkommen / (15 - 2 * logMoveHist) + 1) > .8)
            //{
            //    ;
            //}
            if (mychilds.ContainsKey(pos))
            {
                mychilds[pos].calculateMCTSResult();
                return mychilds[pos].wert;
            }
            //if (myparent!= null && myparent.mychildOppRaveVorkommen.ContainsKey(pos))
            //{
            //    double theret = (mychildRaveGewonnen[pos] + c + 0.5) / (mychildRaveVorkommen[pos] + 1);
            //    double gamma = getgamma(this, pos);
            //    theret = (1 - gamma) * theret;
            //    theret += gamma * ((myparent.mychildOppRaveGewonnen[pos] + c + 0.5) / (myparent.mychildOppRaveVorkommen[pos] + 1));
            //    theret += bias;
            //    return theret;
            //}
            //if (myRootBoard.myboardsize > 9)
            //{

            //    bias = GetBiasForTreeSelect19(pos);
            //}

            return (mychildRaveGewonnen[pos] + c + 0.5) / (mychildRaveVorkommen[pos] + 1) + mychildBias[pos] / ((vorkommen + 1) / (15 - 2 * logMoveHist) + 1);

        }



        private void calculateMCTSResult()
        {
            double beta = getbeta(this);
            double ucb1 = c * Math.Sqrt(Math.Log(myparent.vorkommen + 1) / (vorkommen + 1));
            //double ucb1 = 0;
            double u_RAVE = 0;
            double uNormal = 0;
            //if (myRootBoard.mytoMove == color.white)
            //{
            uNormal = (1 - beta) * (gewonnen + 0.5) / (vorkommen + 1);
            //}

            u_RAVE = beta * (gewonnen_RAVE + 0.5) / (vorkommen_RAVE + 1);
            //if (myparent != null  && myparent.myparent!= null && myparent.myparent.mychildOppRaveVorkommen.ContainsKey(pos) && myparent.mychildRaveVorkommen.ContainsKey(pos))
            //{
            //    double gamma = getgamma(this.myparent, pos);
            //    double theret = (1 - gamma) * u_RAVE;
            //    theret += beta * gamma * ((myparent.myparent.mychildOppRaveGewonnen[pos] + c + 0.5) / (myparent.myparent.mychildOppRaveVorkommen[pos] + 1));
            //    u_RAVE = theret;
            //}

            //double u_parent = 0.5;
            ////myRootBoard.mytoMove == color.white
            //if ( myparent != null && myparent.myparent != null && myparent.myparent.mychildRaveVorkommen.ContainsKey(pos))
            //{
            //    u_parent = (myparent.myparent.gewonnen - (myparent.vorkommen_RAVE - myparent.gewonnen_RAVE) + 0.5) / (myparent.myparent.vorkommen - myparent.myparent.mychildRaveVorkommen[pos] + 1);

            //}

            //wert = uNormal + u_RAVE + ucb1 + bias + (u_parent - 0.5) * (myparent.vorkommen + 1) / ((myparent.vorkommen + 1) * (vorkommen_RAVE + 1));
            wert = uNormal + u_RAVE + ucb1 + mybias / (myparent.vorkommen / (15 - 2 * logMoveHist) + 1);
            // to have a very little advantage for moves with more points
            wert += myresultpoints / 10000000;
            q = (double)gewonnen / (double)vorkommen;
            qr = (double)gewonnen_RAVE / (double)vorkommen_RAVE;
            //return wert;
        }


        /// <summary>
        /// writes a list of moves with its values 
        /// </summary>
        public void writeTreeRoot()
        {
            if (myRootBoard.myGame.myRegression > 0) return;
            if (myRootBoard.myGame.myisGTP && !myRootBoard.myGame.myisGTPDebug) return;
            Console.WriteLine("# " + Game.chatstring(myRootBoard.myGame));
            foreach (string theline in getRootTreemoves().Split('/'))
            {
                Console.WriteLine(theline);
            }

        }

        /// <summary>
        /// writes a list of moves with its values 
        /// </summary>
        public string getRootTreemoves()
        {
            string theReturn = "";
            var sortedDict = from entry in mychilds.Values where entry != null orderby entry.vorkommen descending, entry.wert descending, entry.qr descending select entry;
            foreach (Tree cNode in sortedDict)
            {
                double beta = getbeta(cNode);
                theReturn += "#" + cNode.pos.ToString("000")
                                    + ": gew:" + cNode.gewonnen.ToString("0000")
                                    + " vor:" + cNode.vorkommen.ToString("0000")
                                    + " q:" + ((double)cNode.gewonnen / (double)cNode.vorkommen).ToString("0.000")
                                    + " geR:" + cNode.gewonnen_RAVE.ToString("00000")
                                    + " voR:" + cNode.vorkommen_RAVE.ToString("00000")
                                    + " q:" + ((double)cNode.gewonnen_RAVE / (double)cNode.vorkommen_RAVE).ToString("0.000")
                                    + " wer:" + cNode.wert.ToString("0.000")
                                    + " beta:" + beta.ToString("0.000") + "/";
                //+ " uN:" + uNormal.ToString("00.00")
                //+ " uR:" + u_RAVE.ToString("00.00")
                //+ " ucb1:" + ucb1.ToString("00.00")
                //+ " beta:" + beta.ToString("00.00")

            }
            return theReturn;
        }

        public static double getbeta(Tree cNode)
        {
            double beta = cNode.vorkommen_RAVE / (cNode.vorkommen_RAVE + cNode.vorkommen + 4 * b * b * cNode.vorkommen_RAVE * cNode.vorkommen);
            return beta;
        }

        //public static double getgamma(Tree cNode, int pos)
        //{
        //    double gamma = cNode.myparent.mychildOppRaveVorkommen[pos] / (cNode.mychildRaveVorkommen[pos] + cNode.myparent.mychildOppRaveVorkommen[pos] + 0.4 * b * cNode.mychildRaveVorkommen[pos] * cNode.myparent.mychildOppRaveVorkommen[pos]);
        //    return gamma;
        //}

        private void writemovePath(Tree theNode)
        {
#if DEBUG
            if (myRootBoard.myGame.myRegression > 0) return;
            try
            {

                Console.SetCursorPosition(mypathlength * 20, Console.CursorTop);
            }
            catch
            {
                ;
            }
            int topnodes = 0;
            ++mypathlength;
            var sortedDict = from entry in theNode.mychilds.Values where entry != null orderby entry.vorkommen descending, entry.qr descending, entry.q descending select entry;
            foreach (Tree cNode in sortedDict)
            {
                ++topnodes;
                //write out top three moves
                string thetext = cNode.pos.ToString("000") + " "
                    + cNode.vorkommen.ToString("000") + " "
                    + (cNode.q * 100).ToString("00.0") + " "
                    + (cNode.qr * 100).ToString("00.0") + " |";
                Console.Write(thetext);
                if (mypathlength < 5 && cNode.mychilds != null && cNode.mychilds.Count > 0)
                {
                    writemovePath(cNode);
                }
                else
                {
                    Console.Write("                   ");
                }
                if (topnodes > writetop || mypathlength > 1) break;
                try
                {
                    Console.SetCursorPosition(0, Console.CursorTop + 1);
                }
                catch { }
            }
            int top = Console.CursorTop - writetop;
            if (top < 0) top = 0;
            if (mypathlength == 1) Console.SetCursorPosition(0, top);
            --mypathlength;
#endif
        }

        private void getTop20PercentSorted(Tree theNode)
        {
            //if (Tree.myRootBoard.mytoMove == color.white)
            //{
            //    //myTopMoves.Clear();
            //    //int c = theNode.mychilds.Count / 2;
            //    //var sortedDict = from entry in theNode.mychilds.Values where entry != null orderby entry.vorkommen descending, entry.qr descending, entry.q descending select entry;
            //    //foreach (Tree cNode in sortedDict)
            //    //{
            //    //    if (c == 0) break;
            //    //    myTopMoves.Add(cNode.pos);
            //    //    --c;
            //    //}
            //}
            //else
            {
                myTopMoves.Clear();
                double minBorder = -100;
                Dictionary<int, double> thetemp = new Dictionary<int, double>();
                foreach (int pos in mychildRaveVorkommen.Keys)
                {
                    if ((double)mychildRaveGewonnen[pos] / mychildRaveVorkommen[pos] > minBorder)
                    {
                        thetemp[pos] = (double)mychildRaveGewonnen[pos] / mychildRaveVorkommen[pos];
                        if (thetemp.Count > 10 || thetemp.Count > mychildRaveVorkommen.Count/10)
                        {
                            double maxBorder = 100;
                            int min1pos = -1;
                            int minpos = -1;
                            foreach (int x in thetemp.Keys)
                            {
                                if (thetemp[x] < maxBorder)
                                {
                                    maxBorder = thetemp[x];
                                    min1pos = minpos;
                                    minpos = x;
                                }
                                else
                                if (min1pos > -1 && thetemp[x] < thetemp[min1pos])
                                {
                                    min1pos = x;
                                }
                            }
                            thetemp.Remove(minpos);
                            if (min1pos >= 0) minBorder = thetemp[min1pos];
                        }
                    }
                }
                myTopMoves.AddRange(thetemp.Keys);

                int c = theNode.mychilds.Count / 2;
                var sortedDict = from entry in theNode.mychilds.Values where entry != null orderby entry.vorkommen descending, entry.qr descending, entry.q descending select entry;
                foreach (Tree cNode in sortedDict)
                {
                    if (c == 0) break;
                    if (!myTopMoves.Contains(cNode.pos))
                    {
                        myTopMoves.Add(cNode.pos);
                    }
                    --c;
                }
            }
        //    myOppTopMoves.Clear();
        //    double min = -100;
        //    foreach(int pos in mychildOppRaveVorkommen.Keys)
        //    {
        //        thetemp[pos] = (mychildOppRaveGewonnen[pos] + 0.5) / (mychildOppRaveVorkommen[pos] + 1);
                
        //    }
        //    var sortedDict1 = from entry in thetemp orderby entry.Value descending select entry;
        //    foreach(KeyValuePair<int, double> item in sortedDict1)
        //    {
        //        myOppTopMoves.Add(item.Key);
        //        if (myOppTopMoves.Count > myTopMoves.Count) break;
        //        if (myOppTopMoves.Count > thetemp.Count / 5) break;
        //    }

        //    //Console.Write(myTopMoves.Count.ToString() + " ");
        }
        public void writealive()
        {
            for (int x = 0; x < myRootBoard.myboardsize; ++x)
            {
                Console.Write("| " + x.ToString("00") + " ");
            }
            Console.Write("|");
            for (int y = 0; y < myRootBoard.myboardsize; ++y)
            {
                Console.WriteLine("");
                Console.Write("|");
                for (int x = 0; x < myRootBoard.myboardsize; ++x)
                {
                    int pos = x + y * myRootBoard.myboardsize;
                    if (!myRootBoard.myGroupPosition.ContainsKey(pos))
                    {
                        Console.Write("    ");
                    }
                    else
                    {
                        if (myRootBoard.myGroup[myRootBoard.myGroupPosition[pos]].myColor == color.black)
                        {
                            Console.Write(" B" + getalivepercent(myRootBoard.myGroup[myRootBoard.myGroupPosition[pos]]).ToString("00"));
                        }
                        else
                        {
                            Console.Write(" W" + getalivepercent(myRootBoard.myGroup[myRootBoard.myGroupPosition[pos]]).ToString("00"));
                        }
                    }
                    Console.Write(" ");
                }
                Console.Write("|");
                Console.WriteLine("");
            }
        }
        double getalivepercent(Group CGroup)
        {
            return (double)CGroup.alive*100 / ((double)CGroup.alive + (double)CGroup.dead);
        }
    }
}
